Masala #R108C

Asilbek tarixiy manbalardan qadimiy bir sivilizatsiya haqida bilib oldi. Ushbu sivilizatsiya o‘z davrida juda yuqori darajada rivojlangan bo‘lib, transport tizimi ham shular jumlasidandir. Arxeologik tadqiqotlar natijasida aniqlanishicha, sivilizatsiya eng gullab-yashnagan davrida \(n\) ta shahar mavjud bo‘lgan va ular \(1\) dan \(n\) gacha raqamlangan.

Shaharlar orasida jami \(m\) ta yo‘l mavjud bo‘lib, har bir yo‘l ikki shaharni bog‘laydi. Bir juft shahar orasida bir nechta yo‘l bo‘lishiga ham ruxsat etiladi.

Ma’lumki, ushbu transport tarmog‘i quyidagi ikki shartni qanoatlantirgan:

1. Har qanday yo‘l \(u\) va \(v\) shaharlarini bog‘lasa, u holda
\(1 \le |u - v| \le K\) sharti bajarilishi kerak.

2. Har bir shahar bilan tutashgan yo‘llar soni juft bo‘lishi shart (0 ham juft son hisoblanadi).

Afsuski, aniq transport tarmog‘i bizgacha yetib kelmagan. Sizdan yuqoridagi shartlarni qanoatlantiradigan barcha mumkin bo‘lgan transport tarmoqlari sonini aniqlash talab etiladi.

Ikki xil transport tarmog‘i faqat va faqat shunday holatda turlicha hisoblanadi: agar kamida bitta shahar jufti mavjud bo‘lib, ular orasidagi yo‘llar soni ikki tarmoqda har xil bo‘lsa.

Natija juda katta bo‘lishi mumkinligi sababli, javobni \(10^9 + 7\) ga bo‘lgandagi qoldiqda chiqaring.
 

Kiritish bitta qatordan iborat bo‘lib, unda uchta butun son beriladi:

\(n\), \(m\), \(K\)

Cheklovlar (Constraints)

\(1 \le n \le 30\)

\(0 \le m \le 30\)

\(1 \le K \le 8\)

Izoh:

Transport tarmog‘ida ayrim shaharlar o‘zaro bog‘lanmagan bo‘lishi mumkin.

Bitta butun son chiqaring — yuqoridagi shartlarni qanoatlantiradigan transport tarmoqlari sonining \(10^9 + 7\) ga bo‘lgandagi qoldig‘i.